#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File        :   35.搜索插入位置.py    
@Contact     :   lhouctcs@163.com
@License     :   MIT
@Time        :   2023/2/1 13:11
@Author      :   lhou 
@Version     :   0.1.0
@Description :
"""

# import lib
from typing import List


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 左闭右闭
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (r - l) // 2 + l
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

    def searchInsert_2(self, nums: List[int], target: int) -> int:
        # 左闭右开
        l, r = 0, len(nums)
        while l < r:
            mid = (r - l) // 2 + l
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        return l
